package algorithm.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//二分查找---递归和非递归

/**
 * 二分查找规定数组必须是有序的
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] data ={ 1, 8, 10, 89,1000,1000, 1234 };
        Arrays.sort(data);
        System.out.println(Arrays.toString(data));
//        System.out.println(binarySearch(data, 0, data.length - 1, 999));
        List<Integer> list = binarySearch2(data, 0, data.length - 1, 1000);
        System.out.println(list);
    }


    //递归版---原数组不重复
    public static int binarySearch(int[]data,int left,int right,int key){
        if (left>right){
            return -1;
        }
        int mid = (right+left)/2;

        if (key>data[mid]){
           return binarySearch(data,mid+1,right,key);
        }else if (key<data[mid]){
           return binarySearch(data,left,mid-1,key);
        }else {
            return mid;
        }

    }



    //递归版---原数组有重复数据
    public static List<Integer> binarySearch2(int[]data, int left, int right, int key){

        if (left>right){
            return new ArrayList<Integer>();
        }
        int mid = (right+left)/2;

        if (key>data[mid]){
            return binarySearch2(data,mid+1,right,key);
        }else if (key<data[mid]){
            return binarySearch2(data,left,mid-1,key);
        }else {
            List<Integer> list =   new ArrayList<>();
            int temp = mid-1;
            while (true){
                if (temp< 0|| data[temp]!=key){
                    break;
                }
                list.add(temp);
                temp--;
            }
            list.add(mid);
            temp = mid+1;
            while (true){
                if (temp>data.length-1 || data[temp]!=key){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }

    }
}
